import { CheckAns } from "./CheckAns";

namespace LeetCode0480MedianSlidingWindow {

    // 没啥想法，直接动手处理 (数组无排序，先取窗口大小排序；后续增减不需要复杂的排序了)
    function medianSlidingWindow(nums: number[], k: number): number[] {
        // 题设 k 始终有效，即：k 始终小于等于输入的非空数组的元素个数(题目提示是错的！！！)
        if (!nums || !k || nums.length < k) return [];
        let ans: number[] = new Array();
        let winCap = nums.slice(0, k).sort((a, b) => { return a - b; });
        const isEven: boolean = k % 2 == 0;
        if (isEven) {
            ans.push((winCap[Math.floor(k / 2)] + winCap[Math.floor((k - 1) / 2)]) / 2);
        } else {
            ans.push(winCap[Math.floor(k / 2)]);
        }
        // 后续数据处理
        for (let i = k; i < nums.length; i++) {
            // 移除即将出视窗的数据
            winCap.splice(winCap.indexOf(nums[i - k]), 1);
            // 二分查找插入位置
            let posL = 0;
            let posR = k - 1;
            while (posL <= posR) {
                const mid = Math.floor((posR + posL) / 2);
                if (winCap[mid] <= nums[i]) {
                    posL = mid + 1;
                }
                else {
                    posR = mid - 1;
                }
            }
            winCap.splice(posR + 1, 0, nums[i]);
            if (isEven) {
                ans.push((winCap[Math.floor(k / 2)] + winCap[Math.floor((k - 1) / 2)]) / 2);
            } else {
                ans.push(winCap[Math.floor(k / 2)]);
            }
        }
        return ans;
    };

    // test
    const testData: { ary: number[], k: number, ans: number[] }[] = [
        { ary: [1, 3, -1, -3, 5, 3, 6, 7], k: 3, ans: [1, -1, -1, 3, 5, 6] }
    ];
    for (const data of testData) {
        const ans = medianSlidingWindow(data.ary, data.k);
        CheckAns(data, ans);
    }
}